1. Field of the Invention
The invention relates generally to methods and apparatus for generating and displaying isosurfaces. In particular, the invention relates to methods and apparatus for generating isosurfaces given input data that includes (1) the representation of a set of points in three-dimensional space; (2) connectivity information with respect to the set of points, i.e., information concerning how to form a geometric shape utilizing the given set of points; and (3) a scalar field, i.e., a single scalar value associated with each point in said set of points such as, for example, temperature, etc., for the purpose of volumetric data visualization.
The methods and apparatus contemplated by the invention allow the desired isosurfaces to be produced efficiently on all hardware platforms including those not equipped to rapidly generate such isosurfaces using normally computation intensive processes. Further aspects of the invention are directed to (1) methods and apparatus which support the selective display of isosurface and contour line images, and to (2) methods and apparatus which utilize parallel processing techniques to enhance the efficiency of isosurface "image data" generation, where the term "image data" as used herein is defined as a data structure that may be utilized by, for example, a commercially available graphics package to actually produce the display image.
2. Description of the Related Art
The following additional definitions will be used herein in connection with describing the background of the invention and the invention per se:
(1) An "isosurface" is defined as a surface in three-dimensional space on which all scalar field values are constant (i.e., are equal). PA1 (2) A "scalar field" is defined as a set of scalar values (each value being a single real number), each associated with a point in three-dimensional space. PA1 (3) A "contour line" is defined as a curve in three-dimensional space on which all scalar field values are constant (i.e., are equal). PA1 (4) A "triangle" is defined as a region conformally mapable into a plane bounded by three edges with common vertices. PA1 (5) A "tetrahedron" is defined as a volumetric region bounded by four triangular patches with common edges. PA1 (6) An "isolevel" is defined as the scalar value associated with either an isosurface or a contour line. PA1 (7) An "isofacet" is defined as a bounded subdivision of an isosurface. PA1 (a) decomposing the mesh into tetrahedra; PA1 (b) identifying the isofacet vertices on the edges of each tetrahedral subelement; and PA1 (c) connecting the vertices together as triplets to form triangular isofacets.
In performing scientific and engineering analysis, it is often desirable to examine a scalar field mapped over a discretized volume, referred to in the field of finite element analysis as a "mesh".
Such scalar fields may represent stress values within a mechanical object, pressure or temperature of a fluid flow, or other physical phenomena occurring within (or on the boundary of) a volumetric region.
To visualize results interactively utilizing a digital computer, having an associated storage device and interactive display facilities, it is highly desirable to present users with isosurfaces of constant scalar value in order to visualize the behavior of measurable physical phenomena in three-dimensional space.
Means for computing isosurface image data, which can then be used to produce a display utilizing commercially available graphics packages, are known in the prior art and are referred to herein as "isosurface generators" In general, the full shape of an isosurface cannot be expressed in closed form; therefore, the known isosurface generators utilize approximations to generate the isosurface image data utilized to actually render an isosurface image.
Several well known approximation methods exist, including those that globally fit high-order curved surfaces to input geometric and scalar field data as taught, for example, by Lancaster and Salkauskas, in "Curve and Surface Fitting: An Introduction", published in 1986 by Academic Press. However, global surface-fitting is often a computationally intensive process and to perform such processes, specialized, expensive, processing hardware would be required.
Alternate approaches for generating isosurfaces are known, i.e., approaches that do not rely on global surface fitting, as typified by the use of the polyhedra approximation techniques taught in an article by Koide, Doi and Kajioka entitled "Polyhedral Approximation Approach To Molecular Orbital Graphics", published in the Journal of Molecular Graphics 4 (1986), at pages 149-160. This publication is hereby incorporated by reference.
Koide et al, teaches an isosurface generator that performs the following steps to create isosurface image data:
For the final step, Koide et al specify that the connection of the vertices and the number of isofacets produced within the tetrahedron are specified based only upon the presence of vertices on tetrahedron edges.
Utilizing such teaching, additional processing would then be required to determine the specific edges containing the vertices to be connected. This additional processing is largely repetitive, resulting once again in the isosurface generation being computationally intensive, very time-consuming and therefore slow in response.
In contrast to the teachings of Koide et al, prior art isosurface generators, such as the one taught by Koyamada in Japanese published patent application 3-127188 entitled "Method and Apparatus For Generating Images", are known which do not use intermediate geometric data (in particular, Koide et al's triangles) to represent isosurfaces and which can produce isosurface image data without having input connectivity information. In particular, Japanese published patent application 3-127188 utilizes the property that all isosurfaces within a tetrahedron have the same normal vector, and the fact that scalar values change linearly along any segment, to generate isosurface image data.
Such approaches to isosurface image data generation are problematic in that the resultant image data can not be used to dynamically reposition isosurface images, nor can the image data be used to display surface contour lines since no connectivity information and surface geometry are defined.
Prior art specifically directed to displaying isosurface image data (as opposed to generating such data) is also known and referred to herein as further background material to illustrate the state of the art. For example, Japanese published patent application 3-202981 entitled "Method and System for 3D Graphics", teaches methods for displaying isosurface image data that enable a user to get a quick response for displaying isosurfaces with hidden surfaces processed from a 3D grid data without special graphic hardware.
Other prior art teachings, such as the teachings by Behm et al found in U.S. Pat. No. 5,150,457, assigned to the same assignee as the present invention (entitled "Enhanced Visualization Using Translucent Contour Surfaces"), and the aforementioned Japanese published patent application 3-127188 reference, also relate to methods and apparatus useful for displaying isosurface image data.
None of the known prior art methods and apparatus used for displaying isosurface image data are suitable for selectively display isosurfaces and surface contour lines occurring at user-selected isolevels where the isolevels are chosen from a set of predefined scalar values. Such a capability would provide for an enhanced degree of user interactivity and permit more detailed analysis of phenomena represented by the isosurface images.
Finally, Koyamada in an article entitled "A Method To Reconstruct Solid Elements Into Linear Tetrahedral Elements", published in IBM Technical Disclosure Bulletin, Vol. 32, No. 1, June 1989, pp. 340-2, sets forth further background material useful in understanding the present invention. In this reference Koyamada describes the general concept of creating display data from three-dimensional finite analysis output by first creating a "tetraset", i.e., by converting all elements which a three-dimensional region consists of, into linear tetrahedral elements. It will be seen hereinafter that the present invention makes use of this concept for generating isosurface image data.
In view of the prior art described hereinabove, and indeed in view of the present state of the art, it would be desirable to provide methods and apparatus which allow the aforementioned visualization of isosurfaces to be performed on less sophisticated hardware platforms than taught in the prior art, e.g., those isosurfaces generators which globally fit high-order curved surfaces to input geometric and scalar field data.
Furthermore, it would be desirable if such methods and apparatus facilitated a high degree of interactivity between the user and system utilized to display isosurface image data. For example, it would be desirable if the selective display of isosurfaces and surface contour lines were supported, along with the ability to selectively display isosurfaces and surface contour lines occurring at user-selected isolevels, where the isolevels are chosen from a set of predefined scalar values. It would also be desirable to provide the user with the ability to interactively reposition a displayed image.
Still further, it would be desirable to provide methods and apparatus for generating isosurface image data that could take advantage of present day parallel processing techniques to improve the efficiency of the image data generation process, and to improve overall system responsiveness to user requests (for example, to aid in repositioning an image being displayed), etc.